package Greedy.leetcode;

import java.util.Arrays;

/**
 * 1. 问题描述
 *      数轴上放置了一些筹码，每个筹码的位置存在数组chips当中。
 *      你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：
 *      将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
 *      将第 i 个筹码向左或者右移动 1 个单位，代价为 1。
 *      最开始的时候，同一位置上也可能放着两个或者更多的筹码。
 *      返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。
 *
 * 2. 算法分析
 *      注意理解题意：
 *          position = [2,2,2,3,3]
 *          其中position[0] = 2 表示位置2上有三个筹码
 *          一般的position[i]表示位置
 *
 *     1. 暴力法   时间复杂度高O(nlogn+n^2)  不推荐
 *
 *     2.
 *
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 玩筹码 {
    public static void main(String[] args) {
        int[] a = {1,2,3};
        System.out.println(minCostToMoveChips1(a));
    }

    /**
     * 暴力法
     * @param position
     * @return
     */
    public static int minCostToMoveChips1(int[] position) {
        Arrays.sort(position);
        int mincost = Integer.MAX_VALUE;
        for(int i = 0; i < position.length; i++) {
            // 以当前位置position[i]为基准
            int curcost = 0;
            for(int j = 0; j < i; j++) {
                curcost += (position[i]-position[j]) % 2;
            }
            for(int j = position.length-1; j > i; j--) {
                curcost += (position[j]-position[i]) % 2;
            }
            mincost = Math.min(curcost,mincost);
        }
        return mincost;
    }

    /**
     * 此题主要是考察题意的理解：
     *   就假设当前所有的元素放置到起始位置出，我们判断当前元素的位置是偶数还是奇数
     *   如果是偶数不需要任何代价，就可以放置，如果是奇数，最后只需要一个代价，因为
     *   奇数 % 2 == 1，所以最终需要移动一个位置
     * @param position
     * @return
     */
    public static int minCostToMoveChips2(int[] position) {
        int odd = 0; int even = 0;
        for(int pos : position) {
            if(pos % 2 == 0) {
                odd++;
            } else {
                even++;
            }
        }
        return Math.min(odd,even);
    }


}
